import java.util.LinkedList;
import java.util.Queue;

class Solution {

    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,1,-1};
    static boolean[][] visited;
    static int m;
    static int n;

    public static void solve(char[][] board) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        // 1、先处理边界情况
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m -1 || j == 0 || j == n-1) {
                    if (board[i][j] == 'O') {
                        bfs1(board, i, j); // 将边界需要修改的值全部置为false
                    }
                }
            }
        }
        // 2、扫描内部矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i != 0 && i != m -1 && j != 0 && j != n-1) {
                    if (board[i][j] == 'O'&& !visited[i][j]) {
                        bfs2(board, i, j);// 将'O'修改为'X'
                    }
                }
            }
        }
    }

    private static void bfs1(char[][] board, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int k = 0; k < 4; k++) {
                int sr = arr[0] + dx[k], sc = arr[1] + dy[k];
                if (sr >= 0 && sr < m && sc >= 0 && sc < n 
                    && board[sr][sc] == 'O' && !visited[sr][sc]) {
                        queue.offer(new int[]{sr, sc});
                        visited[sr][sc] = true;
                }
            }
        }
    }

    private static void bfs2(char[][] board, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        board[i][j] = 'X';
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            for (int k = 0; k < 4; k++) {
                int sr = arr[0] + dx[k], sc = arr[1] + dy[k];
                if (sr >= 0 && sr < m && sc >= 0 && sc < n 
                    && board[sr][sc] == 'O' && !visited[sr][sc]) {
                        queue.offer(new int[]{sr, sc});
                        board[sr][sc] = 'X';
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][] board = {
                {'O','O','O'},
                {'O','O','O'},
                {'O','O','O'}
        };
        solve(board);
        System.out.println("sdadad");
    }
}